/**
 * 剑指 Offer 32 - III. 从上到下打印二叉树 III
 * https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/
 */
const { displayNestedArray, createTreeNode } = require('../../libs/public');

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
function levelOrder(root) {
  if (!root) {
    return [];
  }
  let stack = [root];
  const result = [];
  let flag = true;
  while (stack.length) {
    const values = new Array(stack.length).fill(0);
    let i = flag ? 0 : values.length - 1;
    const temp = [];
    while (stack.length) {
      const node = stack.shift();
      values[i] = node.val;
      i += (flag ? 1 : -1);
      if (node.left) {
        temp.push(node.left);
      }
      if (node.right) {
        temp.push(node.right);
      }
    }
    result.push(values);
    stack = temp;
    flag = !flag;
  }
  return result;
}

console.log(displayNestedArray(levelOrder(createTreeNode([3, 9, 20, null, null, 15, 7]))) === '[[3],[20,9],[15,7]]');
